
许多现代编程语言使用类支持面向对象，类是高级语言结构。本节中，我们将探讨如何将类结构映射到LLVM IR中。

\mySubsubsection{5.4.1.}{实现单继承}

类是数据和方法的集合。一个类可以从另一个类继承，可能会添加更多的数据字段和方法，或者覆盖现有的虚函数。我们用Oberon-2中的类来说明这一点，Oberon-2也是一个很好的tinylang模型。Shape类定义了一个具有颜色和面积的抽象类型:

\begin{shell}
TYPE Shape = RECORD
                color: INTEGER;
                PROCEDURE (VAR s: Shape) GetColor(): INTEGER;
                PROCEDURE (VAR s: Shape) Area(): REAL;
             END;
\end{shell}

GetColor方法只返回颜号:

\begin{shell}
PROCEDURE (VAR s: Shape) GetColor(): INTEGER;
BEGIN RETURN s.color; END GetColor;
\end{shell}

抽象形状的面积无法计算，所以这是一种抽象的方法:

\begin{shell}
PROCEDURE (VAR s: Shape) Area(): REAL;
BEGIN HALT; END;
\end{shell}

Shape类型可以扩展为表示Circle类:

\begin{shell}
TYPE Circle = RECORD (Shape)
                radius: REAL;
                PROCEDURE (VAR s: Circle) Area(): REAL;
              END;
\end{shell}

对于一个圆，面积则可以计算:

\begin{shell}
PROCEDURE (VAR s: Circle) Area(): REAL;
BEGIN RETURN 2 * radius * radius; END;
\end{shell}

该类型也可以在运行时查询。若形状是Shape类型的变量，则可以这样制定类型测试:

\begin{shell}
IF shape IS Circle THEN (* … *) END;
\end{shell}

除了语法不同之外，其工作原理与C++非常相似。但显著区别是Oberon-2语法显式声明了this指针，将其称为方法的接收方。

要解决的基本问题是如何在内存中布局类，如何实现方法的动态调用和运行时类型检查。对于内存布局，Shape类只有一个数据成员，可以将其映射到相应的LLVM结构类型:

\begin{shell}
@Shape = type { i64 }
\end{shell}

Circle类添加了另一个数据成员，解决方案是在末尾附加新的数据成员:

\begin{shell}
@Circle = type { i64, float }
\end{shell}


原因是一个类可以有很多子类。使用这种策略，公共基类的数据成员始终具有相同的内存偏移量，并且使用相同的索引通过getelementptr指令访问相应的字段。

为了实现方法的动态调用，必须进一步扩展LLVM结构。若在Shape对象上调用Area()函数，则调用抽象方法，从而导致应用程序停止。若在Circle对象上调用，则调用相应的方法来计算圆的面积。另一方面，可以为这两个类的对象调用GetColor()函数。

实现这一点的基本思想是，将一个表与每个对象的函数指针关联起来。这里，表有两个信息:一个用于GetColor()方法，另一个用于Area()函数。Shape类和Circle类都有这样一个表。这些表在Area()函数的条目中有所不同，该函数根据对象的类型调用不同的代码。这个表称为虚函数表，通常缩写为vtable。

虚函数表本身没有用，必须把它和一个对象关联起来，总是添加指向虚函数表的指针，作为该结构的第一个数据成员。在LLVM级别，@Shape类型是这样的:

\begin{shell}
@Shape = type { ptr, i64 }
\end{shell}

@Circle类型也进行了类似的扩展。

得到的内存结构如图5.1所示:

\myGraphic{0.7}{content/part2/chapter5/images/1.png}{图5.1 - 类和虚函数表的内存布局}

LLVM IR中，Shape类的虚函数表可以可视化为如下表示，其中两个指针对应于GetColor()和GetArea()方法，如图5.1所示:

\begin{shell}
@ShapeVTable = constant { ptr, ptr } { GetColor(), Area() }
\end{shell}

此外，LLVM没有void指针，而是使用指向字节的指针。随着隐藏虚值表字段的引入，现在还需要有一种方法来初始化它。C++中，这是调用构造函数的一部分。在Oberon-2中，该字段在分配内存时自动初始化。

然后，通过以下步骤执行对方法的动态调用:

\begin{enumerate}
\item
通过getelementptr指令计算虚函数表指针的偏移量。

\item
加载指向虚参表的指针。

\item
计算函数在虚函数表中的偏移量。

\item
加载函数指针。

\item
使用调用指令通过指针间接调用函数。
\end{enumerate}

还可以在LLVM IR中可视化对虚拟方法(如Area())的动态调用。首先，从Shape类的相应指定位置加载一个指针。下面的load表示将指针加载到实际的虚函数表中，以便形成函数:

\begin{shell}
// Load a pointer from the corresponding location.
%ptrToShapeObj = load ptr, ...
// Load the first element of the Shape class.
%vtable = load ptr, ptr %ptrToShapeObj, align 8
\end{shell}

之后，getelementptr获取偏移量以调用Area():

\begin{shell}
%offsetToArea = getelementptr inbounds ptr, ptr %vtable, i64 1
\end{shell}

然后，加载指向Area()的函数指针:

\begin{shell}
%ptrToAreaFunction = load ptr, ptr %offsetToArea, align 8
\end{shell}

最后，通过指针调用Area()函数：

\begin{shell}
%funcCall = call noundef float %ptrToAreaFunction(ptr noundef
  nonnull align 8 dereferenceable(12) %ptrToShapeObj)
\end{shell}

即使在单继承的情况下，生成的LLVM IR也可能看起来非常冗长。尽管生成对方法的动态调用过程看起来效率不高，但大多数CPU架构只需两条指令就可以执行该动态调用。

此外，要将函数转换为方法，还需要对对象数据的引用，需要通过将指向数据的指针作为方法的第一个参数来实现的。在Oberon-2中，这是明确的接收者。在类似C++的语言中，是隐式this指针。

使用虚函数表，每个类在内存中都有唯一地址。这对运行时类型测试也有帮助吗?是的，但帮助有限。为了说明这个问题，用一个继承自Circle类的Ellipse类来扩展类层次，这不是数学意义上的is-a关系。

若有一个Shape类型的shape变量，则可以实现shape IS Circle类型的测试，将shape变量中存储的虚表指针与Circle类的虚表指针进行比较。只有当shape具有确切的Circle类型时，这种比较才会为true。但若shape是Ellipse类型，则比较返回false。但在需要Circle类型对象的所有地方，都可以使用Ellipse类型的对象。

解决方案是使用运行时类型信息扩展虚函数表，需要存储多少信息取决于源语言。为了支持运行时类型检查，存储一个指向基类虚函数表的指针就足够了，如图5.2所示:

\myGraphic{0.8}{content/part2/chapter5/images/2.png}{图5.2 - 支持简单类型测试的类和虚函数表布局}

若测试失败，则使用指向基类的虚函数表的指针重复测试。重复此操作，直到测试结果为true；若没有基类，则为false。与调用动态函数相比，类型测试是一个代价高昂的操作，最坏的情况下，继承层次结构可以向上回溯到根类。

若了解整个类层次结构，就有一种有效的方法:按照深度优先的顺序，对类层次结构的每个成员进行编号。类型测试变成了对一个数字或一个间隔进行比较，这可以在恒定的时间内完成。事实上，这就是LLVM自己的运行时类型测试的方法，我们在前一章中已经了解过了。

将运行时类型信息与虚函数表耦合是一种设计决策，要么是源语言强制要求的，要么只是作为实现细节。例如，语言在运行时支持反射，所以需要详细的运行时类型信息，并且数据类型没有vtable，将两者耦合就不是一个好主意。在C++中，耦合会导致具有虚函数(因此没有虚函数表)的类，没有运行时的类型数据。

通常，编程语言支持的接口是虚拟方法的集合。接口很重要，提供了有用的抽象。我们将在下一节中查看接口的可能实现方式。

\mySubsubsection{5.4.2.}{使用接口扩展单继承}

Java等语言支持接口，接口是抽象方法的集合，类似于没有数据成员、只定义了抽象方法的基类。接口带来了一个有趣的问题，实现接口的每个类，都可以在虚函数表中的不同位置拥有相应的方法。原因很简单，虚函数表中函数指针的顺序，是从语言源码中类定义中的函数顺序派生出来的。接口的定义与此无关，不同的顺序是标准。

接口中定义的方法可以有不同的顺序，可以将每个实现的接口的表附加到类中。对于接口的每个方法，这个表可以指定该方法在虚函数表中的索引，也可以指定存储在虚函数表中的函数指针的副本。若在接口上调用方法，则搜索接口对应的虚函数表，获取指向该函数的指针，并调用该方法。在Shape类中添加两个I1和I2接口会产生以下布局:

\myGraphic{0.7}{content/part2/chapter5/images/3.png}{图5.3 - 接口虚函数表的布局}

需要注意的是，必须找到合适的表。可以使用类似于运行时类型测试的方法:在接口虚函数表中执行线性搜索。可以为每个接口分配唯一编号(例如，一个内存地址)，并使用这个编号来标识这个虚函数表。这种方案的缺点是显而易见的:通过接口调用方法比在类上调用相同的方法要花费更多的时间，但要解决这个问题并不容易。

一个好的方法是用哈希表代替线性搜索。在编译时，类实现的接口是已知的，以可以构造一个完美的哈希函数，将接口编号映射到接口的虚函数表。在构造过程中可能需要标识接口的唯一编号，还有其他方法可以计算唯一编号。若源码中的符号名称唯一，则可以计算该符号的加密哈希(例如MD5)，并使用该哈希作为数字。计算在编译时进行，没有运行时成本。

结果比线性搜索快得多，只需要常数时间。不过，会涉及数的几个算术操作，比类类型方法调用要慢。

通常，接口也参与运行时类型测试，使列表搜索更长。若实现了哈希表方法，也可以用于运行时类型测试。

有些语言允许有多个父类。这对实现有一些有趣的挑战，我们将在下一节中了解这些。

\mySubsubsection{5.4.3.}{增加对多重继承的支持}

多重继承增加了另一个挑战。若一个类继承自两个或多个基类，则需要以一种仍然可以从方法访问的方式组合数据成员。与单继承情况类似，解决方案是附加所有数据成员，包括隐藏的虚函数表指针。

Circle类不仅是一个几何形状，而且是一个图形对象。为了对此建模，让Circle类继承Shape类和GraphicObj类。类布局中，Shape类中的字段首先出现，再追加GraphicObj类的所有字段，包括隐藏的虚函数表指针。之后，添加Circle类的新数据成员，得到如图5.4所示的整体结构:

\myGraphic{0.7}{content/part2/chapter5/images/4.png}{图5.4 - 具有多重继承的类和变量的布局}

这种方法有几个含义，可以有多个指向对象的指针。指向Shape或Circle类的指针指向对象的顶部，而指向GraphicObj类的指针指向该对象内部，即嵌入的GraphicObj对象的开始，在比较指针时必须考虑到这一点。

调用虚拟方法也会受到影响，若在GraphicObj类中定义了一个方法，则这个方法需要GraphicObj类的类布局。若在Circle类中没有重写此方法，则有两种可能。若方法调用通过指向GraphicObj实例的指针完成，可以在GraphicObj类的vtable中查找方法的地址并调用该函数。更复杂的情况是，若使用指向Circle类的指针调用该方法，可以在Circle类的虚函数表中查找方法的地址。调用的方法期望this指针是GraphicObj类的一个实例，所以也必须调整那个指针。因为我们知道GraphicObj类在Circle类中的偏移量，所以可以这样做。

若在Circle类中重写了GrapicObj方法，则通过指向Circle类的指针调用该方法，不需要做什么特殊操作。但若该方法是通过指向GraphicObj实例的指针调用，因为该方法需要一个指向Circle实例的this指针，就需要做一些调整。在编译时，因为不知道这个GraphicObj实例是否是多重继承层次结构的一部分，所以无法了解需要调整的部分。为了解决这个问题，我们将再调用方法之前，对this指针进行调整，并将每个函数指针一起存储在虚函数表中，如图5.5所示:

\myGraphic{0.7}{content/part2/chapter5/images/5.png}{图5.5 - vtable与this指针的调整}

一个方法调用现在的过程:

\begin{enumerate}
\item
在虚函数表中查找函数指针。

\item
调整this指针。

\item
调用该方法。
\end{enumerate}

这种方法也可用于实现接口。由于接口只有方法，所以每个实现的接口都会向对象添加一个新的虚函数表指针。这更容易实现，而且很可能更快，但每个对象实例增加了开销。

最坏的情况下，若类有一个64位的数据字段，但是实现了10个接口，则对象需要96字节的内存:8字节用于类本身的虚表指针，8字节用于数据成员，10 * 8字节用于每个接口的虚表指针。

为了支持对对象进行有意义的比较并执行运行时类型测试，需要首先规范指向对象的指针。若在虚函数表中添加一个字段，包含对象顶部的偏移量，则可以调整指针以指向实际对象。在Circle类的实值表中，该偏移量为0，但在嵌入GraphicObj类的实值表中则不是，这是否需要实现取决于源码语言的语义。

LLVM本身并不支持面向对象特性的特殊实现。如本节所示，可以使用可用的LLVM数据类型实现所有方法。正如具有单继承的LLVM IR示例一样，当涉及多继承时，IR可能会变得更加冗长。若想尝试一种新方法，一个好方法就是先用C语言做一个原型。所需的指针操作很快翻译成LLVM IR，但在高级语言中对功能的推理会更容易。

利用本节中获得的知识，可以在自己的代码生成器中实现将编程语言中常见的所有OOP结构简化为LLVM IR。现在，已经掌握了如何表示单继承、使用接口的单继承或内存中的多重继承，以及如何实现类型测试和如何查找虚拟函数，这些都是OOP语言的核心概念。

















































